As an information search device configured to search for a target node from graph structure information expressed by a graph composed of nodes and edges, a device described in Patent Document 1 is known. Graph structure information is information expressing elements configuring intended information as nodes and expressing a relation between the nodes as an edge.
The information search device described in Patent Document 1 executes clustering of graph structure information into subgraphs, and generates a table in which each node is an index and a table in which each edge is an index, for each of the subgraphs. This information search device then searches for a subgraph coincident with a query graph based on these tables.
Further, as another information search device like this, a device described in Non-Patent Document 1 is also known.
The information search device described in Non-Patent Document 1 searches for graph structure information expressed in RDF (Resource Description Framework). This information search device is equipped with a relational database (hereinafter, a database will also be described as a DB) creating part 91, a relational DB 92 and a searching part 93 as shown in FIG. 22. The relational DB 92 stores a class table, a property table, a type table, a resource table, a path table and a triple table as conceptually shown in FIG. 23.
In RDF, information is expressed by a sentence (hereinafter, also referred to as a triple) composed of three elements: a subject, a predicate and an object. A subject represents a resource in an information model, a predicate represents the property of the resource, and an object represents a resource or a property value. Moreover, in a RDF graph visualizing RDF, a resource is expressed by a node, and a property is expressed by an edge (also referred to as an arc).
This information search device registers information into the relational DB 92 in the following manner.
At first, the relational DB creating part 91 generates a class table, a property table, a type table, a resource table and a triple table, respectively, based on a given RDF graph.
Next, the relational DB creating part 91 determines a resource to become a root, and generates connections (arc paths) of all properties from the determined root resource to the respective other resources.
Further, the relational DB creating part 91 provides each of the generated arc paths with path ID (pathID), and registers a path expression (pathexp) representing each of the arc paths and the path ID thereof into the path table. At this moment, a path expression representing an arc path is expressed as a column of property names.
With respect to the relational DB 92 generated in the abovementioned manner, the searching part 93 generates a SQL query and executes search.
In the case of searching for information specified by designation of only a path, the searching part 93 can execute efficient search by using the path table. For example, with respect to the example of the relational DB 92 shown in FIG. 23, in the case of “displaying all of the titles of paintings drawn by someone,” the searching part 93 generates a SQL query designating only a path as shown below and executes search.
 SELECT r.resourceNameFROM path AS p, resource AS rWHERE p.pathID = r.pathIDAND p.pathexp = ‘#title<#paints’
Further, in the case of searching for information which is not specified by designation of only a path, the searching part 93 executes search by using the triple table. Information which is not specified by designation of only a path is a resource referred to with a property that is a resource having a specific value as a property value, a resource referred to with a certain property from a resource having a specific value as a property value, and the like. For example, with respect to the example of the relational DB 92 shown in FIG. 23, in the case of “displaying all of the titles of paintings drawn by Pablo Picasso,” the searching part 93 generates a query as shown below and executes search.
 SELECT t1.objectFROM triple AS t1, triple AS t2, triple AS t3, triple AS t4WHERE t1.predicate = ‘paints’AND t1.subject = t2.subjectAND t2.predicate = ‘first’AND t2.object = ‘Picasso’AND t1.subject = t3.subjectAND t3.predicate = ‘last’AND t3.object = ‘Pablo’
[Patent Document 1] Japanese Unexamined Patent Application Publication No. 2009-258749
[Non-Patent Document 1] Akiyoshi Matono et al., “A Path-based Relational RDF Database,” ADC '05: Proceedings of the 16th Australasian database conference, pp 95-103 (2005)
In the technique described in Patent Document 1, however, because the total number of tuples in the table using edges as indexes increases as graph structure information gets complicated, there is a problem that a time for searching for a subgraph satisfying a query graph increases.
Further, the technique described in Non-Patent Document 1 has a problem that it takes time to search for information which is not specified by designation of only a path.
This is because many join operations are executed at the time of execution of a query that cannot use the path table.
Further, the technique described in Non-Patent Document 1 has a problem that, even in the case of search for information specified by designation of only a path, a searching time increases as an information model gets complicated.
This is because, as an information model gets complicated, the number of tuples in the path table increases. Therefore, in Non-Patent Document 1, even in the case of a query that can use the path table, the number of times of comparison of a path expression to become a search key increases in order of the number of paths, and a searching time largely increases.